package InterfaceOffer;

import java.util.Scanner;

// 3.小熊吃蜂蜜
// 思路：arr1存初始值，arr2交错的存arr1里的两数相加
// 每次遍历arr2，最多遍历k次，寻找arr里的最大值，使其和其前面一个或者后面一个数均-1
// AC: 73%(超时)
public class GLDSolution3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 第一行输入两个整数n和k
        int n = in.nextInt();
        int k = in.nextInt();
        // 第二行输入n罐蜂蜜，每个罐子里有几份
        int arr1[] = new int[n];
        int arr2[] = new int[n - 1];
        for (int i = 0; i < n; i++) {
            arr1[i] = in.nextInt();
        }
        // 初始化arr2
        for (int i = 0; i < n - 1; i++) {
            arr2[i] = arr1[i] + arr1[i + 1];
        }
        // 每次寻找arr2里最大的数的位置，使其前面或者后面的数一起-1
        for (int i = 0; i < k; i++) {
            int maxIndex = findMaxIndex(arr2);
            // 判断前面和后面拿个数比较大
            if (maxIndex == 0) {
                //如果是第一个数，则只能选取"后面的数"
                arr2[maxIndex]--;
                arr2[maxIndex + 1]--;
            } else if (maxIndex == arr2.length - 1) {
                //如果是最后一个数，只能选取"前面的数"
                arr2[maxIndex]--;
                arr2[maxIndex - 1]--;
            } else {
                //首先判断前面和后面哪个数比较大？
                if (arr2[maxIndex + 1] > arr2[maxIndex - 1]) {
                    arr2[maxIndex]--;
                    arr2[maxIndex + 1]--;
                } else {
                    arr2[maxIndex]--;
                    arr2[maxIndex - 1]--;
                }
            }
        }
        // 最后输出arr2里最大的数
        System.out.println(arr2[findMaxIndex(arr2)]);
    }

    // 寻找arr数组里最大的数所对应的下标
    public static int findMaxIndex(int[] arr) {
        int index = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        return index;
    }
}
